package leetcode_1001_1100;

import java.util.HashMap;

public class LeeCode_1092_timeout {
    public static void main(String[] args) {
//        System.out.println(shortestCommonSupersequence("abac", "cab"));
        System.out.println(shortestCommonSupersequence("bcaaacbbbcbdcaddadcacbdddcdcccdadadcbabaccbccdcdcbcaccacbbdcbabb",
                "dddbbdcbccaccbababaacbcbacdddcdabadcacddbacadabdabcdbaaabaccbdaa"));
    }
    private static String shortestCommonSupersequence(String str1, String str2) {
        int[] min = new int[1];
        min[0] = Integer.MAX_VALUE;
        int m = str2.length(), n = str1.length();
        boolean[][] dp = new boolean[m][n];
        HashMap<Integer, String> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = str1.charAt(j) == str2.charAt(i);
            }
        }
        f(str1, str2, dp, map, new StringBuilder(), min, 0, 0);
        return map.get(min[0]);
    }
    private static void f(String str1, String str2, boolean[][] dp, HashMap<Integer, String> map, StringBuilder sb,  int[] min, int i, int j){
        if (i == dp.length - 1 && j == dp[0].length - 1){
            if (dp[i][j]){
                sb.append(str1.charAt(j));
                map.put(sb.length(), sb.toString());
                min[0] = Math.min(min[0], sb.length());
            }else {
                sb.append(str1.charAt(j));
                sb.append(str2.charAt(i));
                map.put(sb.length(), sb.toString());
                min[0] = Math.min(min[0], sb.length());
            }
            return;
        }
        if (dp[i][j]){
            sb.append(str1.charAt(j));
            if (i + 1 < dp.length && j + 1 < dp[0].length){
                f(str1, str2, dp, map, new StringBuilder(sb), min, i + 1, j + 1);
            }else {
                sb.append(i + 1 == dp.length ? str1.substring(j + 1, dp[0].length) : str2.substring(i + 1, dp.length));
                map.put(sb.length(), sb.toString());
                min[0] = Math.min(min[0], sb.length());
            }
        }else {
            if (j + 1 < dp[0].length)
                f(str1, str2, dp, map, new StringBuilder(sb).append(str1.charAt(j)), min, i, j + 1);
            if (i + 1 < dp.length)
                f(str1, str2, dp, map, new StringBuilder(sb).append(str2.charAt(i)), min, i + 1, j);
        }
    }
}
